// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        int n = digits.size();
        if (!n) {
            return vector<string>();
        }

        unordered_map<int, string> phoneMap;
        phoneMap[2] = "abc";
        phoneMap[3] = "def";
        phoneMap[4] = "ghi";
        phoneMap[5] = "jkl";
        phoneMap[6] = "mno";
        phoneMap[7] = "pqrs";
        phoneMap[8] = "tuv";
        phoneMap[9] = "wxyz";

        vector<string> ans;
        string comb;
        dfs(phoneMap, digits, 0, comb, ans);
        return ans;
    }

    void dfs(unordered_map<int, string> phoneMap, string digits, int index, string& comb, vector<string>& ans) {
        if (index == digits.size()) {
            ans.emplace_back(comb);
            return;
        }

        string s = phoneMap[digits[index] - '0'];
        for (char ch : s) {
            comb.push_back(ch);
            // string newComb = comb + ch;
            dfs(phoneMap, digits, index + 1, newComb, ans);
            comb.pop_back();
        }
    }
};